{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Relative Sort Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting-sort #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数排序 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: relativeSortArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的相对排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个数组，<code>arr1</code> 和&nbsp;<code>arr2</code>，<code>arr2</code>&nbsp;中的元素各不相同，<code>arr2</code> 中的每个元素都出现在&nbsp;<code>arr1</code>&nbsp;中。</p>\n",
    "\n",
    "<p>对 <code>arr1</code>&nbsp;中的元素进行排序，使 <code>arr1</code> 中项的相对顺序和&nbsp;<code>arr2</code>&nbsp;中的相对顺序相同。未在&nbsp;<code>arr2</code>&nbsp;中出现过的元素需要按照升序放在&nbsp;<code>arr1</code>&nbsp;的末尾。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]\n",
    "<strong>输出：</strong>[2,2,2,1,4,3,3,9,6,7,19]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 &nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]\n",
    "<strong>输出：</strong>[22,28,8,6,17,44]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr1.length, arr2.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= arr1[i], arr2[i] &lt;= 1000</code></li>\n",
    "\t<li><code>arr2</code>&nbsp;中的元素&nbsp;<code>arr2[i]</code>&nbsp;&nbsp;<strong>各不相同</strong>&nbsp;</li>\n",
    "\t<li><code>arr2</code> 中的每个元素&nbsp;<code>arr2[i]</code>&nbsp;都出现在&nbsp;<code>arr1</code>&nbsp;中</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [relative-sort-array](https://leetcode.cn/problems/relative-sort-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [relative-sort-array](https://leetcode.cn/problems/relative-sort-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,3,2,4,6,7,9,2,19]\\n[2,1,4,3,9,6]', '[28,6,22,8,44,17]\\n[22,28,8,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution(object):\n",
    "    def relativeSortArray(self, arr1, arr2):\n",
    "        count = collections.Counter(arr2)\n",
    "        res = []\n",
    "        ans = []\n",
    "        for i in arr1:\n",
    "            if i in count:\n",
    "                count[i] += 1\n",
    "            else:\n",
    "                res.append(i)\n",
    "        for i in arr2:\n",
    "            ans += [i] * (count[i] - 1)\n",
    "        return ans + sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x:int)->(int,int):\n",
    "            return rank[x] if x in rank else x\n",
    "        n=len(arr2)\n",
    "        rank={x:i-n for i,x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]  # 由于题目说 arr1 的范围在 0-1000，所以生成一个 1001 大小的数组用来存放每个数出现的次数。\n",
    "        ans = []  # 储存答案的数组。\n",
    "        for i in range(len(arr1)):  # 遍历 arr1，把整个arr1的数的出现次数储存在 arr 上，arr 的下标对应 arr1 的值，arr 的值对应 arr1 中值出现的次数。\n",
    "            arr[arr1[i]] += 1  # 如果遇到了这个数，就把和它值一样的下标位置上 +1，表示这个数在这个下标 i 上出现了 1 次。\n",
    "        for i in range(len(arr2)):  # 遍历 arr2，现在开始要输出答案了。\n",
    "            while arr[arr2[i]] > 0:  # 如果 arr2 的值在 arr 所对应的下标位置出现次数大于 0，那么就说明 arr 中的这个位置存在值。\n",
    "                ans.append(arr2[i])  # 如果存在值，那就把它加到 ans 中，因为要按 arr2 的顺序排序。\n",
    "                arr[arr2[i]] -= 1  # 加进去了次数 -1 ，不然就死循环了。\n",
    "        for i in range(len(arr)):  # 如果 arr1 的值不在 arr2 中，那么不能就这么结束了，因为题目说了如果不在，剩下的值按照升序排序。\n",
    "            while arr[i] > 0:  # 同样也是找到大于 0 的下标，然后一直加到 ans 中，直到次数为 0。\n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans  # 返回最终答案。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        result=[]\n",
    "        arr=[]\n",
    "        for i in arr2:\n",
    "            for j in arr1:\n",
    "                if i==j:\n",
    "                    arr.append(j)\n",
    "                    flag=True\n",
    "        for j in arr1:\n",
    "            if j not in arr2:\n",
    "                result.append(j)\n",
    "        result.sort()\n",
    "        return arr+result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        end = []\n",
    "        counter = Counter(arr1)\n",
    "        for i in arr2:\n",
    "            ans.extend([i]*counter[i])\n",
    "        for i in arr1:\n",
    "            if i not in arr2:\n",
    "                end.append(i)\n",
    "        end.sort()\n",
    "        ans.extend(end)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        temp = {}\n",
    "        for i in range(len(arr1)):\n",
    "            if arr1[i] in temp:\n",
    "                temp[arr1[i]] += 1\n",
    "            else:\n",
    "                temp[arr1[i]] = 1\n",
    "        start = 0\n",
    "        for i in arr2:\n",
    "            for _ in range(temp[i]):\n",
    "                arr1[start] = i\n",
    "                start += 1\n",
    "            temp[i] = 0\n",
    "        t = []\n",
    "        for i in temp:\n",
    "            for _ in range(temp[i]):\n",
    "                t.append(i)\n",
    "        t.sort()\n",
    "        for i in t:\n",
    "            arr1[start] = i\n",
    "            start += 1\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        lst1 = []\n",
    "        lst2 = []\n",
    "        lst = []\n",
    "        for i in arr1:\n",
    "            if i in arr2:\n",
    "                lst1.append(i)\n",
    "            else:\n",
    "                lst2.append(i)\n",
    "        for i in arr2:\n",
    "            for j in lst1:\n",
    "                if j == i:\n",
    "                    lst.append(j)\n",
    "        lst.extend(sorted(lst2))\n",
    "        return lst\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3=[False]*(max(arr1)+1)\n",
    "        result=[]\n",
    "        arr4=[i for i in arr1]\n",
    "        for i in arr2:\n",
    "            for j in arr1:\n",
    "                if j == i:\n",
    "                    arr3[i]=True\n",
    "                    result.append(i)\n",
    "                    arr4.remove(i)\n",
    "        arr4=sorted(arr4)\n",
    "        for i in arr4:\n",
    "            result.append(i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return rank[x] if x in rank else x\n",
    "        \n",
    "        n = len(arr2)\n",
    "        rank = {x: i-n for i, x in enumerate(arr2)} # 下标相对于n的差值, 差值越大越靠前\n",
    "        # 由于未出现的元素需要出现在末尾, 因此需要将所有元素置为负数, 保证在前\n",
    "        arr1.sort(key=mycmp)  # 根据对应的差值排序\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        max_arr1, min_arr1 = max(arr1), min(arr1)\n",
    "        size = max_arr1 - min_arr1 + 1\n",
    "        counting = [0 for _ in range(size)]\n",
    "\n",
    "        for num in arr1:\n",
    "            counting[num - min_arr1] += 1\n",
    "\n",
    "        res = []\n",
    "        for num in arr2:\n",
    "            while counting[num - min_arr1] > 0:\n",
    "                res.append(num)\n",
    "                counting[num-min_arr1]-=1\n",
    "\n",
    "        for i in range(size):\n",
    "            while counting[i] > 0:\n",
    "                res.append(i + min_arr1)\n",
    "                counting[i] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        end = []\n",
    "        counter = Counter(arr1)\n",
    "        for i in arr2:\n",
    "            ans.extend([i]*counter[i])\n",
    "        for i in arr1:\n",
    "            if i not in arr2:\n",
    "                end.append(i)\n",
    "        end.sort()\n",
    "        ans.extend(end)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            while i in arr1:\n",
    "                res.append(i)\n",
    "                arr1.remove(i)\n",
    "        return res + sorted(arr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        #思路：从arr1种挨个遍历，如果2中的元素在1中，则拿到列表new1中，否则拿到new2中。将两个新的new进行拼接\n",
    "        new1 = []\n",
    "        new2 = []\n",
    "        for i in arr2:\n",
    "            for j in arr1:\n",
    "                if i == j :\n",
    "                    new1.append(j)\n",
    "        #         else:\n",
    "        #             new2.append(j)   # 这么做报错了，是因为每次把重复的元素都添加到了new2中\n",
    "        # new2.sort()\n",
    "        # zui = new1 + new2\n",
    "        # return zui\n",
    "\n",
    "    \n",
    "\n",
    "        filtered_list = [item for item in arr1 if item not in arr2]\n",
    "        filtered_list.sort()\n",
    "        zui1 = new1 + filtered_list\n",
    "        return zui1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        tmp = [0 for _ in range(1001)]\n",
    "        ans = []\n",
    "\n",
    "        for i in arr1:\n",
    "            tmp[i] += 1\n",
    "\n",
    "        for i in arr2:\n",
    "            ans.extend([i] * tmp[i])\n",
    "            tmp[i] = 0\n",
    "\n",
    "        for i in range(1001):\n",
    "            if tmp[i] > 0:\n",
    "                ans.extend([i] * tmp[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        temp=Counter(arr1)\n",
    "        res=[]\n",
    "        res2=[]\n",
    "        for aa in arr2:\n",
    "            res.extend([aa]*temp[aa])\n",
    "        for aa in arr1:\n",
    "            if aa not in arr2:\n",
    "                res2.append(aa)\n",
    "        res.extend(sorted(res2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        tmp1=[]\n",
    "        m=0\n",
    "        for i in range(len(arr2)) :\n",
    "            for j in range(len(arr1)) :\n",
    "                if arr1[j]==arr2[i] :\n",
    "                    tmp1.append(arr1[j])\n",
    "                    arr1[j]=10000\n",
    "                    m=m+1\n",
    "        arr1.sort()\n",
    "        tmp1.extend(arr1)\n",
    "        arr1=tmp1\n",
    "        #arr1.remove(-1)\n",
    "        n=len(arr1)\n",
    "        arr1=arr1[:n-m]\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rnk = {num: i for i, num in enumerate(arr2)}\n",
    "        arr1.sort(key = lambda x : (0, rnk[x]) if x in rnk else (1, x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        li, ans, d = list(), list(), Counter(arr1)\n",
    "        for key, value in d.items():\n",
    "            if key not in arr2:\n",
    "                li += [key] * value\n",
    "        for x in arr2:\n",
    "            ans += [x] * d[x]\n",
    "        return ans + sorted(li)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        a1 = Counter(arr1)\n",
    "        s = []\n",
    "        b = []\n",
    "        for i in arr2:\n",
    "            s += [i] * a1[i]\n",
    "            del a1[i]\n",
    "        for j in a1:\n",
    "            b += [j] * a1[j]\n",
    "        b.sort()\n",
    "        return  s + b\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        s = []\n",
    "        cnt = Counter()\n",
    "        for x in arr1:\n",
    "            cnt[x] += 1\n",
    "        for y in arr2:\n",
    "            ans += [y] * cnt[y]\n",
    "        for z in cnt:\n",
    "            if z not in arr2:\n",
    "                s += [z] * cnt[z]\n",
    "        s.sort()\n",
    "        return ans + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def relativeSortArray(self, arr1, arr2):\n",
    "        \"\"\"\n",
    "        :type arr1: List[int]\n",
    "        :type arr2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        out = []\n",
    "        for n in arr1:\n",
    "            a = False\n",
    "            for j in arr2:\n",
    "                if n == j:\n",
    "                    a = True\n",
    "            if not a:\n",
    "                out.append(n)\n",
    "        out.sort()\n",
    "        #print(out)\n",
    "        new = []\n",
    "        for n in arr2:\n",
    "            count = 0\n",
    "            for j in arr1:\n",
    "                if n == j:\n",
    "                    count += 1\n",
    "            if count > 0:\n",
    "                for k in range(count):\n",
    "                    new.append(n)\n",
    "        for n in out:\n",
    "            new.append(n)\n",
    "        return new\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "        # 统计arr1元素的个数\n",
    "        countArr1 = collections.Counter(arr1)\n",
    "\n",
    "        for num in arr2:\n",
    "            for i in range(countArr1[num]):\n",
    "                ans.append(num)\n",
    "        \n",
    "        res = []\n",
    "        for num in arr1:\n",
    "            if num not in set(arr2):\n",
    "                res.append(num)\n",
    "        res.sort()\n",
    "        return ans + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        freq = Counter(arr1)\n",
    "        ans = list()\n",
    "        for n in arr2:\n",
    "            ans.extend([n] * freq[n])\n",
    "            del freq[n]\n",
    "        for m in sorted(list(freq.keys())):\n",
    "            ans.extend([m] * freq[m])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return rank[x] if x in rank else x\n",
    "        \n",
    "        n = len(arr2)\n",
    "        rank = {x: i - n for i, x in enumerate(arr2)} # 下标相对于n的差值, 插值越大越靠前\n",
    "        arr1.sort(key=mycmp)  # 根据对应的差值排序\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            arr1.remove(i)\n",
    "        for i in arr1:\n",
    "            if i in arr2:\n",
    "                arr2.insert(arr2.index(i), i)\n",
    "            else:\n",
    "                res.append(i)\n",
    "        res.sort()\n",
    "        return arr2+res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return rank[x] if x in rank else x\n",
    "        \n",
    "        n = len(arr2)\n",
    "        rank = {x: i - n for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = list()\n",
    "        bins = dict()\n",
    "        temp = list()\n",
    "        for num in arr1:\n",
    "            bins[num] = bins.get(num, 0) + 1\n",
    "        for num in arr2:\n",
    "            res += [num] * bins.get(num)\n",
    "        for num in arr1:\n",
    "            if num not in arr2:\n",
    "                temp.append(num)\n",
    "        res += sorted(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]  # 由于题目说 arr1 的范围在 0-1000，所以生成一个 1001 大小的数组用来存放每个数出现的次数。\n",
    "        ans = []  # 储存答案的数组。\n",
    "        for i in range(len(arr1)):  # 遍历 arr1，把整个arr1的数的出现次数储存在 arr 上，arr 的下标对应 arr1 的值，arr 的值对应 arr1 中值出现的次数。\n",
    "            arr[arr1[i]] += 1  # 如果遇到了这个数，就把和它值一样的下标位置上 +1，表示这个数在这个下标 i 上出现了 1 次。\n",
    "        for i in range(len(arr2)):  # 遍历 arr2，现在开始要输出答案了。\n",
    "            while arr[arr2[i]] > 0:  # 如果 arr2 的值在 arr 所对应的下标位置出现次数大于 0，那么就说明 arr 中的这个位置存在值。\n",
    "                ans.append(arr2[i])  # 如果存在值，那就把它加到 ans 中，因为要按 arr2 的顺序排序。\n",
    "                arr[arr2[i]] -= 1  # 加进去了次数 -1 ，不然就死循环了。\n",
    "        for i in range(len(arr)):  # 如果 arr1 的值不在 arr2 中，那么不能就这么结束了，因为题目说了如果不在，剩下的值按照升序排序。\n",
    "            while arr[i] > 0:  # 同样也是找到大于 0 的下标，然后一直加到 ans 中，直到次数为 0。\n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans  # 返回最终答案。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        n, m = len(arr1), len(arr2)\n",
    "        min_val = min(arr1)\n",
    "        max_val = max(arr1)\n",
    "        arr_num = [0] * (max_val - min_val + 1)\n",
    "        \n",
    "        for num in arr1:\n",
    "            arr_num[num - min_val] += 1\n",
    "        \n",
    "        j, z = 0, 0\n",
    "        new_arr = [0] * n\n",
    "        for i in range(n):\n",
    "            if j < m - 1:\n",
    "                while arr_num[arr2[j]-min_val] == 0:\n",
    "                    j += 1\n",
    "                new_arr[i] = arr2[j]\n",
    "                arr_num[arr2[j]-min_val] -= 1\n",
    "            else:\n",
    "                while arr_num[z] == 0:\n",
    "                    z += 1\n",
    "                new_arr[i] = z + min_val\n",
    "                arr_num[z] -= 1\n",
    "        return new_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        end = []\n",
    "        counter = Counter(arr1)\n",
    "        for i in arr2:\n",
    "            ans.extend([i]*counter[i])\n",
    "        for i in arr1:\n",
    "            if i not in arr2:\n",
    "                end.append(i)\n",
    "        end.sort()\n",
    "        ans.extend(end)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        hashtab1 = dict()\n",
    "        hashtab2 = dict()\n",
    "        not2 = []\n",
    "        for num in arr2:\n",
    "            hashtab2[num] = 1\n",
    "        for num in arr1:\n",
    "            if num in hashtab2:\n",
    "                if num in hashtab1:\n",
    "                    hashtab1[num] += 1\n",
    "                else:\n",
    "                    hashtab1[num] = 1\n",
    "            else:\n",
    "                not2.append(num)\n",
    "        index = 0\n",
    "        for num in arr2:\n",
    "            while hashtab1[num] > 0:\n",
    "                arr1[index] = num\n",
    "                hashtab1[num] -= 1\n",
    "                index += 1\n",
    "        not2.sort(reverse=True)\n",
    "        index = -1\n",
    "        for num in not2:\n",
    "            arr1[index] = num\n",
    "            index -= 1\n",
    "        return arr1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        list1 = []\n",
    "        list2 = arr1.copy()\n",
    "        for i in arr2:\n",
    "            for j in arr1:\n",
    "                if j == i:\n",
    "                    list1.append(j)\n",
    "                    list2.remove(j)\n",
    "        list2.sort()\n",
    "        list1 = list1 + list2\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        \n",
    "        s = Counter(arr1)\n",
    "        res = []\n",
    "        for num in arr2:\n",
    "            if num in s:\n",
    "                res.extend([num] * s[num])\n",
    "        tmp = []\n",
    "        s2 = set(arr2)\n",
    "        for num in arr1:\n",
    "            if num not in s2:\n",
    "                tmp.append(num)\n",
    "        tmp.sort()\n",
    "        return res + tmp\n",
    "\n",
    "        #计数排序\n",
    "        # upper = max(arr1)\n",
    "        # freq = [0] * (upper + 1)\n",
    "        # for x in arr1:\n",
    "        #     freq[x] += 1\n",
    "        # ans = list()\n",
    "        # for x in arr2:\n",
    "        #     ans.extend([x] * freq[x])\n",
    "        #     freq[x] = 0\n",
    "        \n",
    "        # for x in range(upper + 1):\n",
    "        #     if freq[x] > 0:\n",
    "        #         ans.extend([x] * freq[x])\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def get_key(x,l1,l2):\n",
    "            a = 1 #len(l1)+1\n",
    "            b = x #l2.index(x)\n",
    "            if x in l2:\n",
    "                a = 0\n",
    "                b = l2.index(x)\n",
    "            return (a,b)\n",
    "        arr1.sort(key = lambda x:get_key(x,arr1,arr2))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        res1 = []\n",
    "        dir = {}\n",
    "\n",
    "\n",
    "        for i in range(len(arr2)):\n",
    "            dir[arr2[i]] = 0\n",
    "\n",
    "        for i in arr1:\n",
    "            num = dir.get(i, \"null\")\n",
    "            if num == \"null\":\n",
    "                res1.append(i)\n",
    "            else:\n",
    "                dir[i] += 1\n",
    "\n",
    "        keys = dir.keys()\n",
    "\n",
    "        for i in keys:\n",
    "            n = dir[i]\n",
    "            for k in range(n):\n",
    "                res.append(i)\n",
    "\n",
    "        res = res + sorted(res1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dic1 = {}\n",
    "        for v in arr1:\n",
    "            if v not in dic1:\n",
    "                dic1[v] = 1\n",
    "            else:\n",
    "                dic1[v] += 1\n",
    "        result = []\n",
    "        for v in arr2:\n",
    "            result.extend([v]*dic1[v])\n",
    "            dic1.pop(v)\n",
    "        reserve = sorted(list(dic1.keys()))\n",
    "        for k in reserve:\n",
    "            result.extend([k]*dic1[k])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        return sorted(arr1,key=lambda x:(0,arr2.index(x)) if x in arr2 else (1,x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        count = {}\n",
    "        new_arr = []\n",
    "        not_used = []\n",
    "        for num in arr1:\n",
    "            count[num] = count.get(num, 0) + 1\n",
    "            if num not in arr2:\n",
    "                not_used.append(num)\n",
    "        not_used.sort()\n",
    "        for num in arr2:\n",
    "            for i in range(count[num]):\n",
    "                new_arr.append(num)\n",
    "        for num in not_used:\n",
    "            new_arr.append(num)\n",
    "\n",
    "        return new_arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        cache = []\n",
    "        index_to_find = 0\n",
    "        max_index = len(arr2)-1\n",
    "        for number in arr1:\n",
    "            if number not in arr2:\n",
    "                cache.append(number)\n",
    "        cache.sort()\n",
    "\n",
    "        temp = {}\n",
    "        for number in arr1:\n",
    "            if temp.get(number) is None:\n",
    "                temp[number] = [number]\n",
    "            else:\n",
    "                temp[number].append(number)\n",
    "        ans = []\n",
    "        for number in arr2:\n",
    "            ans += temp.get(number)\n",
    "\n",
    "        return ans+cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr2 += sorted(set(arr1)-set(arr2))\n",
    "        arr1.sort(key=arr2.index)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mycmp(x: int) -> (int, int):\n",
    "            return rank[x] if x in rank else x\n",
    "        \n",
    "        n = len(arr2)\n",
    "        rank = {x: i-n for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=mycmp)\n",
    "        return arr1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: \n",
    "        arr1=sorted(arr1)\n",
    "        ac1=collections.Counter(arr1)\n",
    "        ac2=collections.Counter(arr2)\n",
    "        new=[]\n",
    "        \n",
    "        \n",
    "        for num in ac2:\n",
    "            if ac1[num]!=0:\n",
    "                new.extend([num]*ac1[num])\n",
    "                ac1[num]=0\n",
    "        for num in ac1:\n",
    "            if ac1[num]!=0:\n",
    "                new.extend([num]*ac1[num])\n",
    "        return new\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3 = []\n",
    "        arr4 = []\n",
    "        for item2 in arr2:\n",
    "            for i, item1 in enumerate(arr1):\n",
    "                if item1 == item2:\n",
    "                    arr3.append(item1)\n",
    "                if item1 not in arr2:\n",
    "                    del arr1[i]\n",
    "                    arr4.append(item1)\n",
    "        # arr4.sort()\n",
    "        for i in range(0, len(arr4)):\n",
    "            min_index = i\n",
    "            for j in range(i+1, len(arr4)):\n",
    "                if arr4[min_index] > arr4[j]:\n",
    "                    min_index = j\n",
    "            arr4[i], arr4[min_index] = arr4[min_index], arr4[i]\n",
    "        arr3.extend(arr4)\n",
    "        return arr3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            for k, v in enumerate(arr1):\n",
    "                if v == i:\n",
    "                    res.append(v)\n",
    "            while i in arr1:\n",
    "                arr1.remove(i)\n",
    "        arr1.sort()\n",
    "        return res + arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            count = arr1.count(i)\n",
    "            while count != 0:\n",
    "                res.append(i)\n",
    "                count -= 1\n",
    "                arr1.remove(i)\n",
    "        res = res + sorted(arr1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 遍历arr2的元素，得出该元素在arr1中出现的次数\n",
    "# 在arr1中出现几次，那么就将该元素重复几次加入列表res\n",
    "# 并在arr1中对应移除 已加入列表res中的元素\n",
    "# 拼接相对arr2位置排序的res 和 排序剩余元素的arr1 ， 并返回结果\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dic = Counter(arr1)\n",
    "        c = sorted(list(set(arr1) - set(arr2)))\n",
    "        ans = []\n",
    "        for n in arr2 + c:\n",
    "            ans += [n] * dic[n]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        state = dict()\n",
    "        n = len(arr2)\n",
    "        for i in range(0,len(arr2)):\n",
    "            state[arr2[i]] = i\n",
    "        for i in range(0,len(arr1)):\n",
    "            if arr1[i] in state.keys():\n",
    "                arr1[i] = [state[arr1[i]],arr1[i]]\n",
    "            else:\n",
    "                arr1[i] = [n+arr1[i],arr1[i]]\n",
    "        arr1.sort()\n",
    "        for i in range(0,len(arr1)):\n",
    "            arr1[i] = arr1[i][1]\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        n = len(arr1)\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            count = arr1.count(i)\n",
    "            while count != 0:\n",
    "                res.append(i)\n",
    "                count -= 1\n",
    "                arr1.remove(i)\n",
    "        res = res + sorted(arr1)\n",
    "        return res\n",
    "\n",
    "# 遍历arr2的元素，得出该元素在arr1中出现的次数\n",
    "# 在arr1中出现几次，那么就将该元素重复几次加入列表res\n",
    "# 并在arr1中对应移除 已加入列表res中的元素\n",
    "# 拼接相对arr2位置排序的res 和 排序剩余元素的arr1 ， 并返回结果\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        adds = []\n",
    "        for i in arr1:\n",
    "            if i in arr2:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                adds.append(i)\n",
    "        return sorted(res,key = lambda x:arr2.index(x))+sorted(adds)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rnk = defaultdict(int)\n",
    "        for i, num in enumerate(arr2) :\n",
    "            rnk[num] = i\n",
    "        arr1.sort(key = lambda x : (0, rnk[x]) if x in rnk else (1, x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3 = []\n",
    "        arr4 = []\n",
    "        for item2 in arr2:\n",
    "            for i, item1 in enumerate(arr1):\n",
    "                if item1 == item2:\n",
    "                    arr3.append(item1)\n",
    "                if item1 not in arr2:\n",
    "                    del arr1[i]\n",
    "                    arr4.append(item1)\n",
    "        # arr4.sort()\n",
    "        def quick_sort(arr, low ,high):\n",
    "            if low < high:\n",
    "                pivot_index = partition(arr, low, high)\n",
    "                quick_sort(arr, low, pivot_index-1)\n",
    "                quick_sort(arr, pivot_index+1, high)\n",
    "        def partition(arr, low, high):\n",
    "            pivot = arr[low]\n",
    "            left = low + 1\n",
    "            right = high\n",
    "            while left <= right:\n",
    "                while left <= right and arr[left] <= pivot:\n",
    "                    left += 1\n",
    "                while left <= right and arr[right] >= pivot:\n",
    "                    right -= 1\n",
    "                if left <= right:\n",
    "                    arr[left], arr[right] = arr[right], arr[left]\n",
    "            arr[low], arr[right] = arr[right], arr[low]\n",
    "            return right\n",
    "        quick_sort(arr4, 0, len(arr4)-1)\n",
    "        arr3.extend(arr4)\n",
    "        return arr3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        rank = [i for i in range(1001)]\n",
    "        for i in range(len(arr2)):\n",
    "            rank[arr2[i]] = -1000+i\n",
    "        newarr = []\n",
    "        for i in range(len(arr1)):\n",
    "            newarr.append((rank[arr1[i]],arr1[i]))\n",
    "        newarr.sort()\n",
    "        for i in range(len(arr1)):\n",
    "            arr1[i]=newarr[i][1]\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        n = len(arr1)\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            count =  arr1.count(i)\n",
    "            while count != 0:\n",
    "                res.append(i)\n",
    "                count -= 1\n",
    "                arr1.remove(i)\n",
    "        res = res + sorted(arr1)\n",
    "        return res\n",
    "\n",
    "# 遍历arr2的元素，得出该元素在arr1中出现的次数\n",
    "# 在arr1中出现几次，那么就将该元素重复几次加入列表res\n",
    "# 并在arr1中对应移除 已加入列表res中的元素\n",
    "# 拼接相对arr2位置排序的res 和 排序剩余元素的arr1 ， 并返回结果\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans, res = [], []\n",
    "        count = Counter(arr1)\n",
    "        for i in arr2:\n",
    "                ans += [i] * count[i]\n",
    "                del count[i]\n",
    "        for k, v in count.items():\n",
    "            res += [k] * v\n",
    "        res.sort()\n",
    "        ans += res\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        x = {}\n",
    "        temp = []\n",
    "        result = []\n",
    "        for i in arr2:\n",
    "            x[i] = 0\n",
    "        for i in arr1:\n",
    "            if i in x.keys():\n",
    "                x[i] += 1\n",
    "            else:\n",
    "                temp.append(i)\n",
    "        temp.sort()\n",
    "        for i in x.keys():\n",
    "            for j in range(x.get(i)):\n",
    "                result.append(i)\n",
    "        for i in temp:\n",
    "            result.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        c = Counter(arr1)\n",
    "        pre = []\n",
    "        for x in arr2:\n",
    "            if x in c:\n",
    "                pre.extend([x] * c[x])\n",
    "                del c[x]\n",
    "        nex = sorted(list(c.elements()))\n",
    "        return pre + nex\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "\n",
    "        mp = dict()\n",
    "        for i, num in enumerate(arr2):\n",
    "            mp[num] = i\n",
    "        \n",
    "        # 加一个len(arr2)，使得没在arr2里面的值，一定排到在里面的值的后面（升序）\n",
    "        arr1.sort(key=lambda x: mp[x] if x in mp else x + len(arr2))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans, res = [], []\n",
    "        count = Counter(arr1)\n",
    "        for i in arr2:\n",
    "            for j in range(count[i]):\n",
    "                ans.append(i)\n",
    "        arr1 = set(arr1)        \n",
    "        for j in arr1:\n",
    "            if j not in arr2:\n",
    "                for i in range(count[j]):\n",
    "                    res.append(j)\n",
    "        res.sort()\n",
    "        ans += res\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def mysort(x):\n",
    "            return (0, rank[x]) if x in rank else (1,x)\n",
    "        \n",
    "        rank = {x:i for i,x in enumerate(arr2)}\n",
    "        arr1.sort(key=mysort)\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int])->List[int]:\n",
    "        ac = dict(collections.Counter(arr1))\n",
    "        res = []\n",
    "        for n in arr2:\n",
    "            res += ac[n]*[n]\n",
    "            del ac[n]\n",
    "        temp = []\n",
    "        for k, v in ac.items():\n",
    "            temp += [k]*v\n",
    "        temp.sort()\n",
    "        res += temp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        h = {}\n",
    "        ans1 = []\n",
    "        for i in arr2:\n",
    "            h[i] = 0\n",
    "        for i in arr1:\n",
    "            if i in arr2:\n",
    "                h[i] += 1\n",
    "            else:\n",
    "                ans1.append(i)\n",
    "        ans1.sort()\n",
    "        ans = []\n",
    "        for value,num in h.items():\n",
    "            ans += [value] * num\n",
    "        return ans + ans1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        n =len(arr1)\n",
    "        res = []\n",
    "        for i in arr2:\n",
    "            count = arr1.count(i)\n",
    "            while count != 0:\n",
    "                res.append(i)\n",
    "                count -= 1\n",
    "                arr1.remove(i)\n",
    "        res = res + sorted(arr1)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "# 遍历arr2的元素，得出该元素在arr1中出现的次数\n",
    "# 在arr1中出现几次，那么就将该元素重复几次加入列表res\n",
    "# 并在arr1中对应移除 已加入列表res中的元素\n",
    "# 拼接相对arr2位置排序的res 和 排序剩余元素的arr1 ， 并返回结果\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "\n",
    "        mp = dict()\n",
    "        for i, num in enumerate(arr2):\n",
    "            mp[num] = i\n",
    "        \n",
    "        arr1.sort(key=lambda x: mp[x] if x in mp else x + len(arr2))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]  \n",
    "        ans = []  \n",
    "        for i in range(len(arr1)):  \n",
    "            arr[arr1[i]] += 1 \n",
    "        for i in range(len(arr2)): \n",
    "            while arr[arr2[i]] > 0: \n",
    "                ans.append(arr2[i]) \n",
    "                arr[arr2[i]] -= 1 \n",
    "        for i in range(len(arr)): \n",
    "            while arr[i] > 0:  \n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        order = {x: i for i, x in enumerate(arr2)}\n",
    "        arr1.sort(key=lambda x: (x not in order, order.get(x, x)))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        n = max(arr1)\n",
    "        ret = [0]*(n+1)\n",
    "        for i in arr1:\n",
    "            ret[i]+=1\n",
    "        for j in arr2:\n",
    "            for count in range(ret[j]):\n",
    "                ans.append(j)\n",
    "            ret[j]=0\n",
    "        for j in range(n+1):\n",
    "            for count in range(ret[j]):\n",
    "                ans.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        max_arr1, min_arr1 = max(arr1), min(arr1)\n",
    "        size = max_arr1-min_arr1+1\n",
    "        counts = [0 for _ in range(size)]\n",
    "        for num in arr1:\n",
    "            counts[num-min_arr1] += 1\n",
    "        res = []\n",
    "        for num in arr2:\n",
    "            while counts[num-min_arr1] > 0:\n",
    "                res.append(num)\n",
    "                counts[num-min_arr1] -= 1\n",
    "        for i in range(size):\n",
    "            while counts[i] != 0:\n",
    "                res.append(i+min_arr1)\n",
    "                counts[i] -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        dic={}\n",
    "        ex=[]\n",
    "        res=[]\n",
    "        for i in arr1:\n",
    "            if i not in dic:\n",
    "                if i in arr2:\n",
    "                    dic[i]=1\n",
    "                else:\n",
    "                    ex.append(i)\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        for i in arr2:\n",
    "            for j in range(dic[i]):\n",
    "                res.append(i)\n",
    "        ex.sort()\n",
    "        res.extend(ex)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ma = max(arr1)\n",
    "        fre = [0] * (ma + 1)\n",
    "        for num in arr1:\n",
    "            fre[num] += 1\n",
    "        ans = []\n",
    "        for num in arr2:\n",
    "            ans.extend([num] * fre[num])\n",
    "            fre[num] = 0\n",
    "        for i in range(ma + 1):\n",
    "            if fre[i] > 0:\n",
    "                ans.extend([i] * fre[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        d = {v:i for i, v in enumerate(arr2)}\n",
    "        arr1.sort(key = lambda x: (d.get(x, len(arr2)), x))\n",
    "        return arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr = [0 for _ in range(1001)]\n",
    "        ans = []\n",
    "        for i in range(len(arr1)):\n",
    "            arr[arr1[i]] += 1\n",
    "        for i in range(len(arr2)):\n",
    "            while arr[arr2[i]] > 0:\n",
    "                ans.append(arr2[i])\n",
    "                arr[arr2[i]] -= 1\n",
    "        for i in range(len(arr)):\n",
    "            while arr[i] > 0:\n",
    "                ans.append(i)\n",
    "                arr[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr3 = []\n",
    "        arr4 = []\n",
    "        for item2 in arr2:\n",
    "            for i, item1 in enumerate(arr1):\n",
    "                if item1 == item2:\n",
    "                    arr3.append(item1)\n",
    "                if item1 not in arr2:\n",
    "                    del arr1[i]\n",
    "                    arr4.append(item1)\n",
    "        # arr4.sort()\n",
    "        # 快速排序\n",
    "        def quick_sort(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return arr\n",
    "            pivot = arr[len(arr) // 2]\n",
    "            left = [x for x in arr if x < pivot]\n",
    "            middle = [x for x in arr if x == pivot]\n",
    "            right = [x for x in arr if x > pivot]\n",
    "            return quick_sort(left) + middle + quick_sort(right)\n",
    "        arr4 = quick_sort(arr4)\n",
    "        arr3.extend(arr4)\n",
    "        return arr3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        ans2 = []\n",
    "        dict1 = Counter(arr1)\n",
    "        print(dict1)\n",
    "        for i in arr2:\n",
    "            for j in range(dict1[i]):\n",
    "                ans.append(i)\n",
    "        for k,v in dict1.items():\n",
    "            if k not in ans:\n",
    "                for j in range(v):\n",
    "                    ans2.append(k)\n",
    "        ans2.sort()\n",
    "        return ans+ans2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
